package com.lh.jianzhioffer.专项练习.字符串;

import javafx.scene.CacheHint;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: linghao
 * @since: 2023/2/26
 *
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
 *
 * 换句话说，第一个字符串的排列之一是第二个字符串的 子串
 *
 * 回溯算法+递归
 */
public class 字符串中的变位词014 {


    public boolean checkInclusion(String s1, String s2){
        if(s1 == null || s2 == null)return false;
        if(s1.length() > s2.length()) return false;
        if(s1.length() == 0 && s2.length() == 0)return true;
        //s1排列组合结果集
        List<String> list = new ArrayList<>();
        char[] chars = s1.toCharArray();
        //需要排序，避免回溯中的重复
        Arrays.sort(chars);
        boolean[] ret = new boolean[chars.length];
        for(boolean b : ret){
            Arrays.fill(ret,false);
        }
        StringBuilder sb = new StringBuilder();
        huisu(chars,sb,list,ret);

        for(String str : list){
            if(s2.indexOf(str) > -1)return true;
        }
        return false;
    }

    private void huisu(char[] chars, StringBuilder sb, List<String> list, boolean[] ret) {
        if(sb.length() == chars.length){
            list.add(sb.toString());
            return;
        }

        for(int i=0;i<chars.length;i++){
            if(ret[i])continue;
            if(i>0 && chars[i-1]==chars[i] && !ret[i])continue;
            sb.append(chars[i]);
            ret[i] = true;
            huisu(chars,sb,list,ret);
            //回溯
            ret[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
